﻿/**	vec_map.hpp
 *	----	Create Time Stamp	--2009-03-09 01:49:02--
 *------------------------------------------------------------------------------
 *	Mean	:
 *	Author	:Nick Shallery	(nicknide@gmail.com)
 *	Version	:1.0.5.12	(2009-09-13 14:51:38)
 *------------------------------------------------------------------------------
**/	/*YOU HAVE ALL LEFT WITH THIS CODE WHILE YOU KEEP COMMENT IN EVERY COPY.*/

#if			!defined(__LOLIX__TOY__VEC_MAP__NICK__K_IN_G__)
#define		__LOLIX__TOY__VEC_MAP__NICK__K_IN_G__
//==============================================================================
//--------------------------------------------------------------------------


#if			!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)
	#include	"../lolix_cfg.h"
#endif	//	!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)

#if			!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)
	#include	"../lolix_type.h"
#endif	//	!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)
	#include	"./std_algorithm.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_FUNCTIONAL__NICK__K_IN_G__)
	#include	"./std_functional.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_FUNCTIONAL__NICK__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_VECTOR__NICK__K_IN_G__)
	#include	"./std_vector.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_VECTOR__NICK__K_IN_G__)

#if			!defined(__LOLIX__TOY__PAIR_TYPE__K_IN_G__)
	#include	"./pair_type.hpp"
#endif	//	!defined(__LOLIX__TOY__PAIR_TYPE__K_IN_G__)

#if			!defined(__LOLIX_TOY__STD_ALGORITHM__NICK__K_IN_G__)
	#include	"./std_algorithm.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)


#if			LOLIX_CFG__IS_DEBUG
	#define		__LOLIX_TMP__DEFINE__CHECK_VALID(v)	__check_valid(v)
#else	//	LOLIX_CFG__IS_DEBUG
	#define		__LOLIX_TMP__DEFINE__CHECK_VALID(v)
#endif	//	LOLIX_CFG__IS_DEBUG


namespace lolix{namespace toy{

template<typename _TKey, typename _TMap, typename _TLess, typename _TAlc>
class vec_multimap
{
	typedef	lolix::toy::pair<_TKey, size_type>	_T_Pos;
	typedef	lolix::toy::vector<_T_Pos, _TAlc> _T_Key;
	typedef lolix::toy::vector<_TMap, _TAlc> _T_Val;
	typedef	typename type::type_choise<type::type_equal<_TLess, void>::value, less, _TLess>::type	_T_LessType;
	_T_Key		_vkey;
	_T_Val		_vval;
	_T_LessType	_less_cmp;
	typedef	vec_multimap<_TKey, _TMap, _TLess, _TAlc>		this_type;
	typedef	lolix::toy::pair<_TKey const&, _TMap&>			_TVal;
	typedef	lolix::toy::pair<_TKey const&, const _TMap&>	_TCVal;
public:
	typedef	_T_LessType		less_type;
	typedef	_TVal			value_type;
	typedef	_TCVal			const_value_type;
	typedef	_TCVal const&	const_reference;
	typedef	_TCVal const*	const_pointer;
	typedef	_TVal&			reference;
	typedef	_TVal*			pointer;
	typedef	_TMap			mapped_type;
	typedef	_TKey			key_type;
	typedef	size_type		size_type;
	typedef	difference_type	difference_type;
	typedef	typename	type::pass_type<value_type>::const_value_type	const_pass_type;
	typedef typename	type::pass_type<key_type>::const_value_type		const_key_pass_type;
	typedef	typename _TAlc::rebind<this_type>::other		allocator_type;

	#pragma region	// iterator and const_iterator and reverse_iterator and const_reverse_iterator
	class	_T_CIterator
		{
			typedef	_T_CIterator					this_type;
		protected:
			typedef	vec_multimap<_TKey, _TMap, _TLess, _TAlc>	container_type;
			friend	container_type;

		public:
			typedef std::random_access_iterator_tag iterator_category;
			typedef typename container_type::value_type		value_type;
			typedef typename container_type::const_value_type		const_value_type;

			//typedef container_type::difference_type	difference_type;
			//typedef difference_type				distance_type;	// retained
			typedef typename container_type::pointer		pointer;
			typedef typename container_type::reference		reference;
			typedef typename container_type::const_pointer	const_pointer;
			typedef typename container_type::const_reference	const_reference;

			LOLIX_INLINE_CALL	_T_CIterator(void)
				: _vec(0)
				, _pos(0)
				, _init(0)
				{
				}

			LOLIX_INLINE_CALL	const_reference operator*(void)const
				{
				return *__get();
				}

			LOLIX_INLINE_CALL	const_pointer operator->(void)const
				{
				return __get();
				}

			LOLIX_INLINE_CALL	this_type& operator ++(void)
				{
				return (*this).operator += (1);
				}
			LOLIX_WARNING_FOR_PERFORMANCE("use prefix increment operator instead")
			LOLIX_INLINE_CALL	this_type operator ++(int)
				{
				this_type tmp(*this);
				++(*this);
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type&	operator --(void)
				{
				return (*this).operator -= (1);
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix decrement operator instead")
			LOLIX_INLINE_CALL	this_type	operator --(int)
				{
				this_type tmp(*this);
				--(*this);
				return tmp;
				}
			LOLIX_INLINE_CALL	this_type&	operator += (difference_type pos)
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				_pos += pos;
				_init = 0;
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type&	operator -= (difference_type pos)
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				_pos -= pos;
				_init = 0;
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type	operator + (difference_type pos)const
				{
				this_type tmp(*this);
				tmp += pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type	operator - (difference_type pos)const
				{
				this_type tmp(*this);
				tmp -= pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	difference_type	operator-(const this_type& o)const
				{
				DO_IN_DEBUG_MODEL(__check_same_ct(o));
				return this->_pos - o._pos;
				}

			LOLIX_INLINE_CALL	const_reference operator[](difference_type pos)const
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(pos);
				return *(this->__get()+pos);
				}
#undef		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC
#define		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(__lx_v__)		\
			LOLIX_INLINE_CALL	bool operator __lx_v__ (const this_type& o)const{DO_IN_DEBUG_MODEL(__check_same_ct(o));return this->_pos __lx_v__ o._pos;}
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(==);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(!=);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(<);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(<=);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(>);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(>=);
#undef		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC

		protected:
			LOLIX_INLINE_CALL	_T_CIterator(const container_type* o, size_type pos)
				: _vec(o)
				, _pos(pos)
				, _init(0)
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				}

			LOLIX_INLINE_CALL	const const_pointer __get(void)const
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				if ( !_init )
					{
					new ((void*)_value_buf) const_value_type(_vec->_vkey[_pos].first, const_cast<mapped_type&>(_vec->_vval[_vec->_vkey[_pos].second]));
					_init = 1;
					}
				return (const_pointer)_value_buf;
				}


#if			defined(LOLIX_CFG__IS_DEBUG)
			LOLIX_INLINE_CALL	void __check_valid(difference_type pos)const
				{
				const wchar_t* war = L"invalid lolix::toy::iterator/const_iterator/reference\nbe careself.";
				LOLIX_ASSERT(	_vec
								&& _vec->size() >= _pos	//	引用对象存在， 并且当前范围没有溢出
								&& _pos + pos <= _vec->size()
								&& _pos + pos >= 0
							,	war);
				}

			LOLIX_INLINE_CALL	void	__check_same_ct(const this_type& o)const
				{
				LOLIX_ASSERT(_vec == o._vec, L"invalid container from two lolix::toy::iterator/const_iterator.");
				}
#endif	//	defined(LOLIX_CFG__IS_DEBUG)

			const container_type*	_vec;
			size_type				_pos;
	mutable lx_u32					_init	:	1;					//	是否初始化过下面的内存区
			lx_u8					_value_buf[sizeof value_type];	//	value_type : 惰性计算的一个缓冲区
		};
	friend	_T_CIterator;

	class	_T_Iterator
		: public _T_CIterator
		{
			friend	container_type;
			typedef	_T_Iterator		this_type;
			typedef	_T_CIterator	base_type;
		public:
			typedef base_type::iterator_category	iterator_category;
			typedef typename base_type::value_type			value_type;
			//typedef typename base_type::difference_type		difference_type;
			typedef typename base_type::pointer				pointer;
			typedef typename base_type::reference			reference;
			typedef typename base_type::const_pointer		const_pointer;
			typedef typename base_type::const_reference		const_reference;

			LOLIX_INLINE_CALL	_T_Iterator(void): base_type(){}

			LOLIX_INLINE_CALL	reference operator* (void)
				{
				return *__get();
				}

			LOLIX_INLINE_CALL	pointer operator -> (void)
				{
				return &(**this);
				}
			LOLIX_INLINE_CALL	this_type& operator++ (void)
				{
				base_type::operator++();
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix increment operator instead")
			LOLIX_INLINE_CALL	const this_type operator++(int)
				{
				this_type tmp(*this);
				++*this;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type& operator-- (void)
				{
				base_type::operator--();
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix decrement operator instead")
			LOLIX_INLINE_CALL	const this_type operator-- (int)
				{
				this_type tmp(*this);
				--*this;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type& operator += (difference_type pos)
				{
				base_type::operator += (pos);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type& operator -= (difference_type pos)
				{
				base_type::operator -= (pos);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type	operator + (difference_type pos)const
				{
				this_type tmp(*this);
				tmp += pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type	operator - (difference_type pos)const
				{
				this_type tmp(*this);
				tmp -= pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	difference_type	operator-(const this_type& o)const
				{
				DO_IN_DEBUG_MODEL(__check_same_ct(o));
				return this->_pos - o._pos;
				}

			LOLIX_INLINE_CALL	reference	operator [](difference_type pos)const
				{
				return const_cast<reference>(base_type::operator[](pos));
				}


		private:
			LOLIX_INLINE_CALL	_T_Iterator(const container_type* o, size_type pos)
				: _T_CIterator(o, pos)
				{ }
			using base_type::__get;
			LOLIX_INLINE_CALL	pointer __get(void)
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				if ( !_init )
					{
					new ((void*)_value_buf) value_type(_vec->_vkey[_pos].first, const_cast<mapped_type&>(_vec->_vval[_vec->_vkey[_pos].second]));
					_init = 1;
					}
				return (pointer)_value_buf;
				}
		};
	friend	_T_Iterator;

	template<typename t_bidirectional_iterator>
	class _T_reverse_iterator : protected t_bidirectional_iterator
	{
		typedef _T_reverse_iterator<t_bidirectional_iterator>	this_type;
		typedef t_bidirectional_iterator					base_type;

		friend typename base_type::contain_type;
		LOLIX_INLINE_CALL _T_reverse_iterator(base_type b_type): base_type(b_type)
		{ if ( !_id_bind->empty() ) this->__goto_prev__(); }
	public:
		LOLIX_INLINE_CALL _T_reverse_iterator(void){}
		LOLIX_INLINE_CALL this_type& operator++ (void)
			{
			base_type::operator --();
			return *this;
			}
		LOLIX_INLINE_CALL this_type& operator-- (void)
			{
			base_type::operator ++();
			return *this;
			}
		LOLIX_INLINE_CALL const this_type operator++ (int)
			{
			this_type tmp(*this);
			++*this;
			return tmp;
			}
		LOLIX_INLINE_CALL const this_type operator-- (int)
			{
			this_type tmp(*this);
			--*this;
			return tmp;
			}

		using base_type::operator*;
		using base_type::operator->;
		LOLIX_INLINE_CALL bool operator==(this_type const& o)const{return base_type::operator==(o);}
		LOLIX_INLINE_CALL bool operator!=(this_type const& o)const{return base_type::operator!=(o);}
	};


	typedef	_T_CIterator	const_iterator;
	typedef	_T_Iterator		iterator;
	typedef	_T_reverse_iterator<const_iterator>	const_reverse_iterator;
	typedef	_T_reverse_iterator<iterator>	reverse_iterator;

	iterator begin(void){return iterator(this, 0);}
	iterator end(void){return iterator(this, size());}
	const_iterator begin(void)const{return iterator(this, 0);}
	const_iterator end(void)const{return iterator(this, size());}
	LOLIX_INLINE_CALL	reverse_iterator	rbegin(void)
		{
		return reverse_iterator(end());
		}

	LOLIX_INLINE_CALL	const_reverse_iterator rbegin(void)const
		{
		return const_reverse_iterator(end());
		}

	LOLIX_INLINE_CALL	reverse_iterator	rend(void)
		{
		return reverse_iterator(begin());
		}

	LOLIX_INLINE_CALL	const_reverse_iterator rend(void)const
		{
		return const_reverse_iterator(begin());
		}

	#pragma	endregion
	LOLIX_INLINE_CALL vec_multimap<_TKey, _TMap, _TLess, _TAlc>(void)
		{}
	LOLIX_INLINE_CALL vec_multimap<_TKey, _TMap, _TLess, _TAlc>(_TAlc const& alc)
		: _vkey(alc)
		, _vval(alc)
		{ }

	const allocator_type&	get_allocator(void)const
		{
		return _alc;
		}

	LOLIX_INLINE_CALL iterator find(key_type const& key)
		{
		_T_Key::iterator iter = _lower_bound(key);
		if ( iter == _vkey.end() || iter->first != key )
			return end();
		return iterator(this, iter - _vkey.begin());
		}
	LOLIX_INLINE_CALL const_iterator find(key_type const& key)const
		{
		return const_cast<this_type*>(this)->find(key);
		}


	LOLIX_INLINE_CALL size_type	capacity(void)const
		{
		return _vval.capacity();
		}

	LOLIX_INLINE_CALL void clear(void)
		{
		_vkey.clear();
		_vval.clear();
		}

	LOLIX_INLINE_CALL void	reserve(size_type cap)
		{
		_vval.reserve(cap);
		_vkey.reserve(cap);
		}

	LOLIX_INLINE_CALL bool	empty(void)const
		{
		return _vval.empty();
		}

	LOLIX_INLINE_CALL size_type	size(void)const
		{
		return _vval.size();
		}

	LOLIX_INLINE_CALL iterator insert(_TKey const& key, _TMap const& val)
		{
		return __Insert(_lower_bound(key) - _vkey.begin(), key, val);
		}

	LOLIX_INLINE_CALL iterator insert(iterator pos, _TKey const& key, _TMap const& val)
		{
		LOLIX_ASSERT(pos._vec == this, L"迭代器容器匹配错误");
		//	pos->first > prv, and pos->first < next
#if			LOLIX_CFG__IS_DEBUG
		if ( empty() )
		{
			LOLIX_ASSERT(pos == end(), L"空容器中, 建议插入位置不是 back");
		}
		else
		{
			if ( pos != end() )
			{
				LOLIX_ASSERT(!_less_cmp(pos->first, key), L"建议插入容器的位置不符");
			}
			else
			{
				LOLIX_ASSERT(!_less_cmp(key, _vkey.back().first), L"建议插入容器的位置不符");
			}
		}
#endif	//	LOLIX_CFG__IS_DEBUG
		return __Insert(_lower_bound(pos, key) - _vkey.begin(), key, val);
		}


	LOLIX_INLINE_CALL iterator insert(const_pass_type data)
		{
		return insert(data.first, data.second);
		}


	LOLIX_INLINE_CALL iterator insert(iterator pos, const_pass_type data)
		{
		return insert(pos, data.first, data.second);
		}

	template<typename _TPair>
	LOLIX_INLINE_CALL iterator insert(_TPair const& v)
		{
		return insert(v.first, v.second);
		}

	LOLIX_INLINE_CALL iterator erase(iterator iter)
		{
		LOLIX_ASSERT(iter._vec == this, L"容器序列有问题， 不是当前容器");
		LOLIX_ASSERT(iter <= end(), L"迭代器越界啦");

		const size_type val_pos = _vkey[iter._pos].second;
		_vkey.erase(_vkey.begin() + iter._pos);
		if ( val_pos == _vval.size() - 1 )
			{
			_vval.pop_back();
			return iter;
			}


		lolix::swap(_vval[val_pos], _vval.back());
		_vval.pop_back();
		for ( size_type i = 0; i != _vkey.size(); ++i )
			{
			if ( _vkey[i].second == _vval.size() )
				_vkey[i].second = val_pos;
			}

		return begin()+iter._pos;
		}

	LOLIX_INLINE_CALL iterator erase(iterator bg, iterator ed)
		{
		for ( ; bg != ed; --ed )
			bg = erase(bg);

		return ed;
		}

	LOLIX_INLINE_CALL iterator erase(const_pass_type val)
		{
			_T_Key::iterator iBegin = _lower_bound(val.first);
			_T_Key::iterator iEnd = _upper_bound(val.first);
			erase(iBegin - _vkey.begin(), iEnd - _vkey.end());
		}

	LOLIX_INLINE_CALL void swap(this_type& o)
		{
		_vkey.swap(o._vkey);
		_vval.swap(o._vval);
		}

	iterator lower_bound(const_key_pass_type key)
		{
		iterator iter = begin() + (_lower_bound(key) - _vkey.begin());
		LOLIX_ASSERT(iter == end() || !_less_cmp(iter->first, key), L"lower_bound 操作结果有误");
		return iter;
		}

	const_iterator lower_bound(const_key_pass_type key)const
		{
		return const_cast<this_type*>(this)->lower_bound(key);
		}

	iterator upper_bound(const_key_pass_type key)
		{
		return begin() + (_upper_bound(key) - _vkey.begin());
		}

	const_iterator upper_bound(const_key_pass_type key)const
		{
		return begin() + (_upper_bound(key) - _vkey.begin());
		}


	LOLIX_INLINE_CALL mapped_type& operator [](key_type const& key)
		{
		iterator iter = find(key);
		if ( iter != end() )
			return iter->second;

		return insert(key, mapped_type())->second;
		}

protected:
	LOLIX_INLINE_CALL iterator __Insert(size_type pos, _TKey const& key, _TMap const& val)
		{
		_vkey.insert(_vkey.begin()+pos, lolix::toy::make_pair(key, _vval.size()));
		_vval.push_back(val);
		return iterator(this, pos);
		}

	LOLIX_INLINE_CALL void __Erase(size_type posBegin, size_type posEnd)
		{
		LOLIX_ASSERT(posBegin <= posEnd && posEnd <= _vkey.size(), L"删除对象的时候迭代器越界");
		for ( ; posBegin != posEnd; ++posBegin )
			{
			const size_type pos = _vkey[posBegin];
			_vkey.erase(_vkey.begin()+pos);
			if ( pos == _vkey.size() )
				{
				_vval.pop_back();
				continue;
				}

			for ( size_type i = 0; i != _vkey.size(); ++i )
				{
				if ( _vkey[i] != _vkey.size() )
					continue;
				_vkey[i] = pos;
				break;
				}

			lolix::swap(_vval[pos], _vval.back());
			_vval.pop_back();
			}
		}

private:
	LOLIX_INLINE_CALL typename _T_Key::const_iterator _lower_bound(_TKey const& key)const
		{
		return lolix::toy::lower_bound(_vkey.begin(), _vkey.end(), key, cmp_pair_first<_T_LessType>(_less_cmp));
		}

	LOLIX_INLINE_CALL typename _T_Key::const_iterator _lower_bound(const_iterator iter_begin, _TKey const& key)const
		{
		return lolix::toy::lower_bound(_vkey.begin() + (iter_begin - begin()), _vkey.end(), key, cmp_pair_first<_T_LessType>(_less_cmp));
		}

	LOLIX_INLINE_CALL typename _T_Key::iterator _lower_bound(_TKey const& key)
		{
		return lolix::toy::lower_bound(_vkey.begin(), _vkey.end(), key, cmp_pair_first<_T_LessType>(_less_cmp));
		}

	LOLIX_INLINE_CALL typename _T_Key::iterator _lower_bound(iterator iter_begin, _TKey const& key)
		{
		return lolix::toy::lower_bound(_vkey.begin() + (iter_begin - begin()), _vkey.end(), key, cmp_pair_first<_T_LessType>(_less_cmp));
		}

	LOLIX_INLINE_CALL typename _T_Key::const_iterator _upper_bound(_TKey const& key)const
		{
		return lolix::toy::upper_bound(_vkey.end(), _vkey.end(), key, cmp_pair_first<_T_LessType>(_less_cmp));
		}

	LOLIX_INLINE_CALL typename _T_Key::iterator _upper_bound(_TKey const& key)
		{
		return lolix::toy::upper_bound(_vkey.end(), _vkey.end(), key, cmp_pair_first<_T_LessType>(_less_cmp));
		}
};

template<typename _TKey, typename _TMap, typename _TLess, typename _TAlc>
class vec_map
	: private vec_multimap<_TKey, _TMap, _TLess, _TAlc>
{
	typedef vec_map<_TKey, _TMap, _TLess, _TAlc>		this_type;
	typedef	vec_multimap<_TKey, _TMap, _TLess, _TAlc>	base_type;
	//const static bool is_void_type = type::type_equal<_TLess, void>::value;
	//typedef	type::type_choise<true, lolix::toy::less, _TLess>::type	_T_LessType;
public:
	typedef	typename	base_type::less_type		less_type;
	typedef	typename	base_type::allocator_type	allocator_type;
	typedef typename	base_type::size_type		size_type;
	typedef typename	base_type::difference_type	difference_type;
	typedef typename	base_type::pointer			pointer;
	typedef typename	base_type::const_pointer	const_pointer;
	typedef typename	base_type::reference		reference;
	typedef typename	base_type::const_reference	const_reference;
	typedef typename	base_type::value_type		value_type;
	typedef	typename	base_type::const_iterator	const_iterator;
	typedef	typename	base_type::iterator			iterator;
	typedef	typename	base_type::reverse_iterator	reverse_iterator;
	typedef	typename	base_type::const_reverse_iterator	const_reverse_iterator;
	typedef	typename	base_type::mapped_type		mapped_type;
	typedef	value_type	key_type;

	using base_type::begin;
	using base_type::end;
	using base_type::rbegin;
	using base_type::rend;
	using base_type::get_allocator;

	LOLIX_INLINE_CALL vec_map<_TKey, _TMap, _TLess, _TAlc>(void)
		{ }

	LOLIX_INLINE_CALL vec_map<_TKey, _TMap, _TLess, _TAlc>(_TAlc const& alc)
		: base_type(alc)
		{ }

	using base_type::find;
	using base_type::capacity;
	using base_type::clear;
	using base_type::reserve;
	using base_type::empty;
	using base_type::size;

	LOLIX_INLINE_CALL pair<iterator, bool> insert(const_pass_type val)
		{
		return insert(val.first, val.second);
		}

	LOLIX_INLINE_CALL pair<iterator, bool> insert(_TKey const& key, _TMap const& val)
		{
		pair<iterator, bool> result;
		iterator iter = base_type::lower_bound(key);
		if ( iter == end() || iter->first != key )
			result.first = __Insert(iter-begin(), key, val)
			, result.second = true
			;
		else
			result.first = end()
			, result.second = false
			;
		return result;
		}

	LOLIX_INLINE_CALL iterator insert(iterator pos, _TKey const& key, _TMap const& val)
		{
		LOLIX_ASSERT(base_type::lower_bound(key) == pos && (pos == end() || pos->first != key), L"提供插入的位置错误");
		return base_type::insert(pos, key, val);
		}


	template<typename _TPair>
	LOLIX_INLINE_CALL iterator insert(_TPair const& v)
		{
		return insert(v.first, v.second).first;
		}


	LOLIX_INLINE_CALL iterator insert(iterator pos, const_pass_type data)
		{
		return insert(pos, data.first, data.second);
		}

	void swap(this_type& o)
		{
		base_type::swap(o);
		}

	using base_type::erase;
	using base_type::lower_bound;
	using base_type::upper_bound;

};

}}

namespace lolix{
	template<typename _TKey, typename _TMap, typename _TLess, typename _TAlc>
	LOLIX_INLINE_CALL void swap(toy::vec_multimap<_TKey, _TMap, _TLess, _TAlc>& tl, toy::vec_multimap<_TKey, _TMap, _TLess, _TAlc>& tr)
	{ tl.swap(tr); }
	template<typename _TKey, typename _TMap, typename _TLess, typename _TAlc>
	LOLIX_INLINE_CALL void swap(toy::vec_map<_TKey, _TMap, _TLess, _TAlc>& tl, toy::vec_map<_TKey, _TMap, _TLess, _TAlc>& tr)
	{ tl.swap(tr); }
}

//--------------------------------------------------------------------------
//==============================================================================
#endif	//	!defined(__LOLIX__TOY__VEC_MAP__NICK__K_IN_G__)
